package sort

/**
插入排序的原理是：我们将数组中的数据分为两个区间，已排序区间和未排序区间。初始已排序区间只有一个元素，就是数组的第一个元素。
插入算法的核心思想是取未排序区间中的元素，在已排序区间中找到合适的插入位置将其插入，并保证已排序区间数据一直有序。
重复这个过程，直到未排序区间中元素为空，算法结束。

在这里搭配动态图查看效果更佳：https://visualgo.net/zh/sorting

时间复杂度：插入排序需要两个嵌套的循环，时间复杂度是O(n^2)；
空间复杂度：没有额外的存储空间，是原地排序算法；
算法稳定性：不涉及相等元素位置交换，是稳定的排序算法。
*/
func insertionSort(nums []int) []int {
	if len(nums) <= 1 {
		return nums
	}
	for i := 0; i < len(nums); i++ {
		// 每次从未排序区间取一个数据 value
		value := nums[i]
		// 在已排序区间找到插入位置
		j := i - 1
		for ; j >= 0; j-- { // 已排序区间从后往前比较
			// 如果已排序区间的值比value大，后移
			if nums[j] > value {
				nums[j+1] = nums[j]
			} else { // 如果找到了比value小的值，则退出比较，同时这里j--了，后面就可以把value插入到j+1的位置
				break
			}
		}
		// 插入数据 value
		nums[j+1] = value
	}
	return nums
}